package util;

import java.util.*;

import static util.ArrayUtil.reverseArray;
import static util.GraphUtil.*;
import static util.NumberUtil.BooleanHolder;

/**
 * @author Egor Kulikov (kulikov@devexperts.com)
 */
class GraphAlgorithms {
	public static final int INFINITY = Integer.MAX_VALUE;

	public static class DistanceResult {
		public final int[] distance;
		public final Edge[] last;

		public DistanceResult(int vertexCount) {
			distance = new int[vertexCount];
			Arrays.fill(distance, INFINITY);
			last = new Edge[vertexCount];
		}
	}

	public static DistanceResult dijkstra(Graph graph, int source, boolean ignoreEmptyCapacity) {
		int vertexCount = graph.getVertexCount();
		final DistanceResult result = new DistanceResult(vertexCount);
		result.distance[source] = 0;
		PriorityQueue<Integer> queue = new PriorityQueue<Integer>(vertexCount, new Comparator<Integer>() {
			public int compare(Integer o1, Integer o2) {
				return result.distance[o1] - result.distance[o2];
			}
		});
		queue.add(source);
		while (!queue.isEmpty()) {
			int vertex = queue.poll();
			for (Edge edge : graph.getIncident(vertex)) {
				if (ignoreEmptyCapacity && edge.getCapacity() == 0)
					continue;
				int next = edge.getDestination();
				int newDistance = edge.getWeight() + result.distance[vertex];
				if (result.distance[next] > newDistance) {
					result.distance[next] = newDistance;
					result.last[next] = edge;
					queue.add(next);
				}
			}
		}
		return result;
	}

	private static DistanceResult edgeDistances(Graph graph, int source, final boolean ignoreEmptyCapacity) {
		int vertexCount = graph.getVertexCount();
		final DistanceResult result = new DistanceResult(vertexCount);
		result.distance[source] = 0;
		graph.bfs(source, new BFSCallback() {
			public boolean vertexAdded(Graph graph, Edge edge) {
				if (ignoreEmptyCapacity && edge.getCapacity() == 0)
					return false;
				int destination = edge.getDestination();
				result.distance[destination] = result.distance[edge.getSource()] + 1;
				result.last[destination] = edge;
				return true;
			}

			public void alreadyVisited(Graph graph, Edge edge) {
			}
		});
		return result;
	}

	public static int maximalFlow(Graph graph, int source, final int destination) {
		int totalFlow = 0;
		final Object mock = new Object();
		for (int i = 30; i >= 0; i--) {
			final int flowSize = 1 << i;
			DFSCallback<BooleanHolder, Object> callback = new DFSCallback<BooleanHolder, Object>() {
				public BooleanHolder enterUnvisitedVertex(Graph graph, int vertex, Edge edge, Object p) {
					return new BooleanHolder(vertex == destination);
				}

				public BooleanHolder enterVisitedVertex(Graph graph, int vertex, Edge edge, Object p) {
					return new BooleanHolder(vertex == destination);
				}

				public void exitVertex(Graph graph, int vertex, Edge edge, Object p, BooleanHolder currentResult) {
				}

				public Object beforeUsingEdge(Graph graph, int vertex, Edge edge, Object p,
						BooleanHolder currentResult, Edge nextEdge)
				{
					if (currentResult.value || nextEdge.getCapacity() < flowSize)
						return null;
					if (nextEdge.getDestination() == destination) {
						currentResult.value = true;
						nextEdge.pushFlow(flowSize);
						return null;
					}
					return DFSCallbackAdapter.EMPTY_PARAMETERS;
				}

				public boolean afterVisitingEdge(Graph graph, int vertex, Edge edge, Object p,
						BooleanHolder currentResult, Edge nextEdge, BooleanHolder visitResult, Object pp)
				{
					if (currentResult.value)
						return false;
					if (visitResult == null)
						return true;
					currentResult.value = visitResult.value;
					if (visitResult.value) {
						nextEdge.pushFlow(flowSize);
						return false;
					}
					return true;
				}
			};
			boolean flowExists;
			do {
				flowExists = graph.dfs(source, callback, mock).value;
				if (flowExists)
					totalFlow += flowSize;
			} while (flowExists);
		}
		return totalFlow;
	}

	public static int dinic(Graph graph, int source, int destination) {
		int totalFlow = 0;
		int vertexCount = graph.getVertexCount();
		int[] nextEdge = new int[vertexCount];
		while (true) {
			int[] distance = edgeDistances(graph, source, true).distance;
			if (distance[destination] == INFINITY)
				break;
			Arrays.fill(nextEdge, 0);
			totalFlow += dinicImpl(graph, source, destination, INFINITY, distance, nextEdge);
		}
		return totalFlow;
	}

	private static int dinicImpl(Graph graph, int source, int destination, int flow, int[] distance, int[] nextEdge) {
		if (source == destination)
			return flow;
		if (flow == 0 || distance[source] == distance[destination])
			return 0;
		List<Edge> incident = graph.getIncident(source);
		int incidentSize = incident.size();
		int totalPushed = 0;
		for (int i = nextEdge[source]; i < incidentSize; i++) {
			Edge edge = incident.get(i);
			int nextDestination = edge.getDestination();
			if (distance[nextDestination] != distance[source] + 1)
				continue;
			int pushed = dinicImpl(graph, nextDestination, destination, Math.min(flow, edge.getCapacity()),
				distance, nextEdge);
			if (pushed != 0) {
				edge.pushFlow(pushed);
				flow -= pushed;
				totalPushed += pushed;
				if (flow == 0) {
					nextEdge[source] = i;
					return totalPushed;
				}
			}
		}
		nextEdge[source] = incidentSize;
		return totalPushed;
	}

	public static int[][] floydWarshall(Graph graph) {
		int vertexCount = graph.getVertexCount();
		int[][] distance = new int[vertexCount][vertexCount];
		for (int[] row : distance)
			Arrays.fill(row, Integer.MAX_VALUE);
		for (int i = 0; i < vertexCount; i++) {
			for (Edge edge : graph.getIncident(i))
				distance[i][edge.getDestination()] = edge.getWeight();
		}
		for (int i = 0; i < vertexCount; i++) {
			for (int j = 0; j < vertexCount; j++) {
				for (int k = 0; k < vertexCount; k++) {
					if (distance[j][i] != Integer.MAX_VALUE && distance[i][k] != Integer.MAX_VALUE)
						distance[j][k] = Math.min(distance[j][k], distance[j][i] + distance[i][k]);
				}
			}
		}
		return distance;
	}

	public static int[] topologicalSort(Graph graph, boolean allowCycles) {
		final int[] order = new int[graph.getVertexCount()];
		final boolean[] onPath = new boolean[graph.getVertexCount()];
		final boolean[] hasCycle = new boolean[1];
		graph.fullDFS(new FullDFSCallbackAdapter<Object>() {
			private int index = 0;

			@Override
			public Object enterUnvisitedVertex(Graph graph, int vertex, Edge edge, Object o) {
				onPath[vertex] = true;
				return null;
			}

			@Override
			public Object enterVisitedVertex(Graph graph, int vertex, Edge edge, Object o) {
				if (edge != null && onPath[edge.getDestination()])
					hasCycle[0] = true;
				return null;
			}

			@Override
			public void exitVertex(Graph graph, int vertex, Edge edge, Object o, Object currentResult) {
				order[index++] = vertex;
				onPath[vertex] = false;
			}
		});
		if (hasCycle[0] && !allowCycles)
			return null;
		return order;
	}

	private static class ComponentsCallback implements FullBFSCallback {
		private int componentNumber = -1;
		private final int[] components;

		public ComponentsCallback(int[] components) {
			this.components = components;
		}

		public void bfsStarted(Graph graph, int vertex) {
			components[vertex] = ++componentNumber;
		}

		public boolean vertexAdded(Graph graph, Edge edge) {
			components[edge.getDestination()] = componentNumber;
			return true;
		}

		public void alreadyVisited(Graph graph, Edge edge) {}

	}

	public static int[] components(Graph graph) {
		int[] components = new int[graph.getVertexCount()];
		graph.fullBFS(new ComponentsCallback(components));
		return components;
	}

	public static int[] strongComponents(Graph graph) {
		int[] topologicalOrder = topologicalSort(graph, true);
		reverseArray(topologicalOrder);
		Graph transposed = graph.transposed();
		final int[] components = new int[graph.getVertexCount()];
		transposed.fullBFS(new ComponentsCallback(components), topologicalOrder);
		return components;
	}

	public static DistanceResult levite(Graph graph, int source, boolean ignoreEmptyCapacity) {
		int vertexCount = graph.getVertexCount();
		DistanceResult result = new DistanceResult(vertexCount);
		boolean[] processed = new boolean[vertexCount];
		boolean[] queued = new boolean[vertexCount];
		Deque<Integer> queue = new ArrayDeque<Integer>(vertexCount);
		queue.add(source);
		queued[source] = true;
		result.distance[source] = 0;
		while (!queue.isEmpty()) {
			int vertex = queue.poll();
			queued[vertex] = false;
			processed[vertex] = true;
			for (Edge edge : graph.getIncident(vertex)) {
				if (ignoreEmptyCapacity && edge.getCapacity() == 0)
					continue;
				int destination = edge.getDestination();
				int newDistance = edge.getWeight() + result.distance[vertex];
				if (result.distance[destination] > newDistance) {
					result.distance[destination] = newDistance;
					result.last[destination] = edge;
					if (processed[destination]) {
						processed[destination] = false;
						queued[destination] = true;
						queue.addFirst(destination);
					} else if (!queued[destination]) {
						queued[destination] = true;
						queue.add(destination);
					}
				}
			}
		}
		return result;
	}

	public static int[] minCostFlow(Graph graph, int source, int destination, boolean maxFlowRequired) {
		int totalFlow = 0;
		int totalCost = 0;
		while (true) {
			DistanceResult result = levite(graph, source, true);
			if (result.distance[destination] >= (maxFlowRequired ? INFINITY : 0))
				return new int[]{totalFlow, totalCost};
			int currentFlow = pushPath(result, source, destination);
			totalFlow += currentFlow;
			totalCost += result.distance[destination] * currentFlow;
		}
	}

	private static int pushPath(DistanceResult result, int source, int destination) {
		int currentVertex = destination;
		int currentFlow = INFINITY;
		while (currentVertex != source) {
			Edge edge = result.last[currentVertex];
			currentFlow = Math.min(currentFlow, edge.getCapacity());
			currentVertex = edge.getSource();
		}
		currentVertex = destination;
		while (currentVertex != source) {
			Edge edge = result.last[currentVertex];
			edge.pushFlow(currentFlow);
			currentVertex = edge.getSource();
		}
		return currentFlow;
	}
}
